两种方法，第一种就是按照规律递归，第二种就是动态规划。
题目
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = “a“
输出: true
解释: 因为 ‘‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:
输入:
s = “ab”
p = “.“
输出: true
解释: “.“ 表示可匹配零个或多个（’*’）任意字符（’.’）。
示例 4:
输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:
s = “mississippi”
p = “misisp*.”
输出: false
思路
其实都是类似于暴力法了，直接考虑到所有的情况然后递归，先是判断是否匹配结束的，匹配结束的标准就是字符串s和字符串p同时用完，所以只需要判断是否同时有j==p.size()和i==s.size(),其中i、j代表s和p中匹配到的字符的下标，接下来就判断匹配过程中可能遇到的两种情况，（*这种情况其实没有必要讨论，因为这种情况其实和一个没有区别，*代表的是有任意个，所以任意个也可以是0个或一个，没有意义）。
第一种情况：
s[i]==p[j]，如果存在p[j+1]那么p[j+1]！=’*’，这种情况下，直接i++、j++之后继续往下比较就可以了，p[j]可以是直接等于s[i]或者等于’.’，对应程序上就写为 if(i<s.size()) return (s[i]==p[j]||p[j]==’.’)&&match(s,p,++i,++j) ,开始这里写成了i++，j++,因为这两者的区别，所以直接传递的就是未加一之后的，所以后来报错，真是个低级错误，尴尬，一般尽量用++i，如果可以的情况下，因为i++会生成一个临时副本，效率会低一点。
第二种情况：
不需要s[i]==p[j]，或者p[j]==’.’，但是p[j+1]存在而且p[j+1]==’‘，这个时候首先认为代表的是前面的字符个数为0，这样直接将p[j]以及p[j+1]跳过，另外一种，不认为代表将前面的字符的个数设置为0，那么这种时候就需要(s[i]==p[j]||p[j]==’.’)为真，才可以让p[j]进入到比对的序列里面去，比对之后，因为不清楚具体的代表的个数，所以不跳过p[j]以及p[j+1]，让它继续和s[i+1]进行比对，因为如果后续比对不上，是可以通过第二种的上一个情况直接将其再跳过的，所以具体的程序逻辑就是return match(s,p,i,j+2)||(i!=s.size()&&(s[i]==p[j]||p[j]==’.’)&&match(s,p,++i,j));
这样不断的进行递归，最后检查出是否满足匹配条件，但是效率很低，存在很多重复子问题，一般存在大量的重复子问题，就可以用动态规划来写，下面第二种方法就介绍动态规划。
code
class Solution {
public:
bool match(string &s,string &p,int i,int j)
{
if(j==p.size())return i==s.size();
if(p.size()-j>1&&p[j+1]=='*')
{
return match(s,p,i,j+2)||(i!=s.size()&&(s[i]==p[j]||p[j]=='.')&&match(s,p,++i,j));
}
else
{
return (i!=s.size()&&(s[i]==p[j]||p[j]=='.')&&match(s,p,++i,++j));//开始写成i++了，超出边界了，
//尴尬了，低级错误
}
}
bool isMatch(string s, string p) {
//递归版本
return match(s,p,0,0);
}
};
思路
动态规划的效率比起上一种方法大概提高了四倍左右的时间，动态规划首先第一个就是建立一个数组（维数视问题复杂度而定，本题建立一个二维的数组），其中dp[i] [j]代表长度为i的s子串，能否用长度为j的p子串进行匹配（从头开始数），可以匹配结果为1，不能为0。首先s和p长度为0的时候肯定可以匹配，那么先将dp[0] [0]置为1，然后开始循环，s的子串长度从0开始（注意一定要从0开始，因为p的开头可能会存在a*这种子串，这是可以在不需要的时候直接忽略掉的，s的子串长度从0开始循环，就可以将它们在有需要的时候忽略掉），直到长度为s的长结束，p的长度是从1开始的，首先因为dp[0] [0]置为1了的，，已经考虑到了两个空子串的情况，其次dp[i] [j]的情况和dp[i] [j-1]有关，所以如果从0开始会经常溢出，并且如果s的子串有长度，而p这边子串为空，那么肯定是匹配不上的，所以就是设置的初始值0.
然后看动态转移方程，起始和上面的方法的情况是一样的，只是用二维数组存储了各种情况下的结果，不用重复计算，节约了很多时间，可以看下面的代码就可以看出来，其实差不多：
首先当j>1时，代表有两个以及以上的元素，如果p[j-1]==’‘，代表现在的p子串的结尾元素是，那么如果说s的子串长度大于0，代表这个子串中是有元素的，那么dp[i] [j]=dp[i-1] [j]&&(s[i-1]==p[j-2]||p[j-2]==’.’);如果说这边算出来的dp[i] [j]为0，那么其实还可以直接通过这个忽略掉前面个字符，所以还可以有dp[i] [j]=dp[i] [j]||dp[i] [j-2];
第二种，最后结尾的字符不等于’*’，那么就是中规中矩的计算是否有dp[i] [j]=dp[i-1] [j-1]&&(p[j-1]==s[i-1]||p[j-1]==’.’);
从两个状态转移方程可以明显看出，情况和上一种是一样的，所以动态规划其实就是找好状态转移方程以及建立好一个数组存储子问题的结果就可以了。
code
class Solution {
public:
bool isMatch(string s, string p) {
int l1=s.size();
int l2=p.size();
vector<vector<int>>dp(l1+1,vector<int>(l2+1,0));
dp[0][0]=1;
for(int i=0;i<=l1;++i)
{
for(int j=1;j<=l2;++j)
{
if(j>1&&p[j-1]=='*')
{
if(i>0)
dp[i][j]=dp[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.');
dp[i][j]=dp[i][j]||dp[i][j-2];
}
else if(i>0)
{
dp[i][j]=dp[i-1][j-1]&&(p[j-1]==s[i-1]||p[j-1]=='.');
}
}
}
return dp[l1][l2];
}
};